public class Test {




}
class Sort{

    // 非递归的归并排序
    // 非递归少了 "分解" 这一步 , 可以手动的就把 数组看成是一个元素一组
    // 一个一组, gap=1 , 直接就继续 和并
    public void mergeSort(int [] array){
        int gap = 1 ;
        while(gap < array.length){
            for (int i = 0; i < array.length; i += 2*gap) {
                int mid = i + gap -1 ;
                int right = mid + gap ;
                if(mid >= array.length){
                    mid = array.length-1 ;
                }
                if(right >= array.length){
                    mid = array.length-1 ;
                }
                merge(array , i , right , mid);
            }
        }
    }






//    // 分解 数组
//    public void mergeSortFunc(int[] array , int left , int right){
//        if(left >= right) return ;
//        int mid = left + right/2 ;
//        // 分解左右两边
//        mergeSortFunc(array, left , mid) ;
//        mergeSortFunc(array, mid+1 , right);
//
//        // 和并左右两边
//        merge(array , left ,right , mid);
//    }
    // 和并两边
    private void merge(int[] array, int left, int right, int mid) {
        int s1 = left;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = right;
        // 新数组
        int[] newArr = new int[right - left + 1];
        int index = 0;
        // 保证两个区间同时有数据
        while (s1 <= e1 && s2 <= e2) {
            if (array[s1] <= array[s2]) {
                newArr[index++] = array[s1++];
            } else {
                newArr[index++] = array[s2++];
            }
        }
        while (s1 <= e1) {
            newArr[index++] = array[s1++];
        }
        while (s2 <= e2) {
            newArr[index++] = array[s2++];
        }
        // 然后将新数组里的值放到 源数组
        for (int i = 0; i < newArr.length; i++) {
            array[i + left] = newArr[i];
        }
    }
}